package hotLeetcode;

import java.util.Arrays;

public class H08Leetcode42 {
    public int trap(int[] height) {
        int len = height.length;
        int[] pre_max = new int[len];
        int[] suf_max = new int[len];
        int result = 0;
        pre_max[0] = height[0];
        for (int i = 1; i < len ; i++) {
            pre_max[i] = Math.max(pre_max[i - 1], height[i]);
        }

        suf_max[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            suf_max[i] = Math.max(height[i], suf_max[i + 1]);
        }

        //遍历 来减
        for (int i = 0; i < len; i++) {
            int min = Math.min(pre_max[i], suf_max[i]);
            result += min - height[i];
        }


        return result;


    }

    public static void main(String[] args) {
        H08Leetcode42 h08Leetcode42 = new H08Leetcode42();
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(h08Leetcode42.trap(height));
    }
}
